// UVa12096 The SetStack Computer
// 刘汝佳/陈锋
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef set<int> Set;
map<Set, int> IDcache; // 把集合映射成ID
vector<Set> Setcache; // 根据ID取集合

// 查找给定集合x的ID。如果找不到，分配一个新ID
int ID (const Set& x) {
  if (IDcache.count(x)) return IDcache[x];
  Setcache.push_back(x); // 添加新集合
  return IDcache[x] = Setcache.size() - 1;
}

int main () {
  ios::sync_with_stdio(false), cin.tie(0);
  int T, n; cin >> T;
  Set empty, x;
  while (T--) {
    stack<int> s; // 题目中的栈
    cin >> n;
    for (int i = 0; i < n; i++) {
      string op; cin >> op;
      if (op[0] == 'P') s.push(ID(empty));
      else if (op[0] == 'D') s.push(s.top());
      else {
        const Set &x1 = Setcache[s.top()]; s.pop();
        const Set &x2 = Setcache[s.top()]; s.pop();
        x.clear();
        if (op[0] == 'U')
          set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), 
            inserter(x, x.begin()));
        if (op[0] == 'I')
          set_intersection(x1.begin(), x1.end(), x2.begin(), x2.end(), 
            inserter(x, x.begin()));
        if (op[0] == 'A') x = x2, x.insert(ID(x1));
        s.push(ID(x));
      }
      cout << Setcache[s.top()].size() << endl;
    }
    cout << "***" << endl;
  }
  return 0;
}
/*
算法分析请参考: 《入门经典-第2版》例题5-5
注意本题中对于set_union以及set_intersection的使用
*/
// Accepted 90ms 1286 C++ 5.3.0 2020-12-18 09:55:14 25860165